NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download". Try It in NetLogo Web

## WHAT IS IT?

Genetic algorithms try to solve a computational problem following some principles of organic evolution. This model has didactic purposes; it is able to give us an answer to the simple arithmetic problem on how to find the highest number composed by a given number of digits. We approach the task using a genetic algorithm, where the possible answers to the problem are represented by agents that in logo programming environment are usually named "turtles".

## HOW IT WORKS

Every turtle owns a “chromosome” made up by a string of digits each one representing a "gene"; chromosomes can mutate on a single gene and can exchange fragments (sequence of genes) with the chromosome carried by other turtles: we can see the mechanism as a mixture of eukaryotic crossing-over and prokaryotic conjugation, here we will refer to it as a genetic-shuffling. The total sequence of genes in a chromosome can be read as a number and its value can be considered the turtles “phenotype” as well as a candidate solution to the problem. A turtle will be as fit as the value expressed by its chromosome will be high. The best theoretical fitness can be easily mathematically established as the nearest to the result of a simple formula. If n is the number of digits in a string, the higher number having n digits is:
(10 ^ n) - 1, that is a sequence of n 9s; on the contrary 10 ^ (n - 1) will give the lower number composed by n digits; in other words, the two formulas give us the extremes of search space.
Only the fittest turtle can conjugate with another turtle giving part of its chromosome. So the best answer is searched fundamentally in two steps: mutation and selective reproduction of (part of) the fittest chromosome by genetic-shuffling.
Mutations happen randomly with a given frequency on just one gene that is a digit place on the chromosome.
Genetic-shuffling takes place between a randomly chosen turtle (recipient) and the most performing one (donor) that offers a fragment of its chromosome to the first one; the two turtles involved in this process will be highlighted by a link. Genetic-shuffling leads to the formation of a new hybrid chromosome made up by the chromosome of the recipient turtle in which a fragment of genes (digits) included between two randomly chosen positions are replaced by the corresponding genes (digits) of one of the donor turtle's chromosome.

## HOW TO USE IT

SETUP button creates the selected number of turtles having a chromosome constituted by a string long till 20 genes (digits), as chosen by the user. Initially, all chromosomes show the lowest suitability.
SEARCH buttons launch a block of instructions that after the detection of the current best and worst chromosomes, recall the genetic-shuffling and mutation operators.
Four displays show some data concerning the last processed genetic-shuffling: the starting point (a-split) and the ending point (b-split) of the donor's fragment insertion (the first extreme is included into the fragment but not the second one) and the number of genes replaced; the resulting hybridized chromosome is reported, as well.
Step by step the less and the most suitable phenotypes (the numerical value of the chromosomal string) are monitored.

## THINGS TO NOTICE

1. During genetic-shuffling, the replaced chromosomal fragment can have random length, so sometimes it can have a null extension or it could cover the entire chromosome but a gene (the fragment's final digit).
2. Because of the strict correspondence between genotype and phenotype, this model doesn't require the computation of a fitness function: such value is enclosed in the same chromosome.
3. In sciences, mathematical language is largely used to describe natural systems and to compute their future evolution. In this case, the language of natural sciences is utilized to compute the solution of an arithmetic problem.

## THINGS TO TRY

Search a possible statistical relationship between the number of cycles required to obtain the right answer to the problem and the single parameters adjustable by sliders. Particularly interesting could be the relationship between mutation rate and the average of cycles' number required to reach the right answer to the problem.
Another approach could be checking if it is more determinant the influence of the random mutations or the selective genetic shuffling or a balanced ratio between the two factors to obtain efficiently the final goal: this feature would require a variation in the code.

## EXTENDING THE MODEL

Minimal Genetic Algorithm can be furtherly extended by adding new routines and plots: e.g. it would be interesting to introduce a block evaluating the genotypes diversity dynamic during the search process.

## NETLOGO FEATURES

In this model, chromosomes have two features: as a string and as a number. To switch them each other, two NetLogo commands are very useful: "read-from-string" interprets the given chromosome and reports the resulting numerical value; on the contrary "word" command allows to revert a number into a string (because it requires two inputs, the second one could be double quotation marks: "")
A third command is useful in mutation and genetic shuffling operators: "replace-item" allows an easy single gene variation as well as a substitution with a chromosome fragment from a donor turtle into the corresponding loci of a recipient turtle.

## RELATED MODELS

- Stonedahl, F. and Wilensky, U. (2008). NetLogo Simple Genetic Algorithm model. http://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

## CREDITS AND REFERENCES

A nice introduction to genetic algorithms could be the chapter nine of the book "Complexity - A guided tour" by Melanie Mitchel (2009 - Oxford University Press) where the GA "Robby the Robot" is described; see also Mitchell, M., Tisue, S. and Wilensky, U. (2012). NetLogo Robby the Robot model http://ccl.northwestern.edu/netlogo/models/RobbytheRobot. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

## COPYRIGHT AND LICENSE

Copyright 2018 Cosimo Leuci.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.